图 | Hikari

1 图的基本概念

1.1 图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，V非空。

有向图
若E是有向边(弧)的有限集合时，图G为有向图，从顶点v到顶点w的弧记为\
无向图
若E是无向边的有限集合，则图G为无向图，v和w之间的边记为(u,w)。
简单图
简单图满足：不存在重复边；不存在顶点到自身的边。
多重图
与简单图相对。
完全图
任意两点之间都存在边的无向图称为无向完全图；任意两个顶点之间都存在两条方向相反的弧的有向图称为有向完全图。
子图
一个图的子图其边和顶点包含于原图中。
连通、连通图和连通分量
顶点v和w之间有路径存在，则称v和w是连通的；图中任意两个顶点均连通的图称为连通图；极大连通子图称为连通分量。
强连通图和强连通分量
有向图中，从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的；
任意一对顶点都是强连通的图称为强连通图；
图的极大强连通子图称为图的强连通分量。
生成树和生成森林
连通图的生成树是包含全部顶点的一个极小连通子图(边数最小)；
非连通图的生成森林是连通分量的生成树的集合。
顶点的度、入度和出度
无向图中顶点的度是以该顶点为端点的边的数目；
有向图中顶点的入度是以该顶点为弧尾的弧的数目；
有向图中顶点的出度是以该顶点为弧头的弧的数目。
边的权和网
边上的数值称为边的权值；边上带权值的图称为网(带权图)。
路径、路径长度和回路
顶点u到w的路径是指从u到w所经过的顶点序列，路径上的边的数目称为路径长度，首尾顶点相同的路径称为回路。
简单路径、简单回路
顶点不重复的路径称为简单路径，顶点不重复的回路称为简单回路。
距离
从顶点u到顶点w的最短路径若存在，则该路径的长度称为从u到w的距离。
有向树
有一个顶点的入度为0，其余顶点入度均为1的有向图称为有向树。

2 图的存储及基本操作

2.1 邻接矩阵法

用一个二维数组存储图中顶点之间邻接关系的信息，则该二维数组称为邻接矩阵。
图的邻接矩阵存储结构描述：

#define MaxVertexNum 100
typedef char VertexType;              //顶点
typedef int EdgeType;                 //边
typedef struct{
    VertexType Vex[MaxVertexNum];      //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];    //邻接矩阵
    int vexnum,arcnum;             //图的当前顶点数和弧数
}MGragn;

2.2 邻接表法

对图G中的每个顶点vi建立一个单链表，单链表中的结点表示依附于该顶点的边，这个单链表称为顶点的边表。顶点的数据信息和边表的头指针建立顶点表，顶点表采用顺序存储。
顶点表：顶点数据域与和指向该顶点的第一条邻接边的指针构成。
边表：邻接点数据域和指向下一条邻接边的指针构成。
图的邻接表存储结构描述：

#define MaxVertexNum 100;
typedef struct ArcNode{    //边表
    int adjvex;             //数据域
    struct ArcNode *next;    //下一条边的指针
    InfoType info;          //权值
}ArcNode;
typedef struct VNode{       //顶点表
    VertexTypeType data;
    ArcNode *first;
}VNode,AdjList[MaxVertexNum];
typedef struct{             
    AdjList vertices;        //邻接表
    int vexnum,arcnum;       //图的顶点数和弧数
}ALGraph;

2.3 十字链表

十指链表是有向图的一种链式存储结构。

2.3 临街多重表

临界多重表是无向图的一种链式存储结构。

3 图的遍历

3.1 图的广度优先搜索(BFS)

算法思想：首先访问起始顶点v，接着依次访问v的各个未被访问的邻接顶点，再对这些邻接顶点进行与v相同的操作，直到图中所有顶点全部访问。

#define MaxVertexNum 100
bool visited[MaxVertexNum];
void BFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++)     //初始化访问位为未访问
        visited[i]=FALSE;
    InitQueue(Q);                   //初始化队列
    for(int i=0;i<G.vexnum;i++){    //遍历每个顶点
        if(!visited[i])
            BFS(G,i,Q);
    }
}
void BFS(Graph G,int v,Queue Q){
    visit(v);               //访问操作
    visited[v]=TRUE;        //设置顶点为已访问
    EnQueue(Q,v);           //顶点入队
    while(!IsEmpty(Q)){
        DeQueue(Q,v)         //顶点出队
        for(int w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w)){   //遍历邻接顶点
            if(!visited[w]){            //先访问再入队
                visit(w);
                visited[w]=TRUE;
                EnQueue(Q,w);
            }
        }
    }
}

BFS算法性能分析

	邻接表	邻接矩阵
时间复杂度	O(V+E)	O(V ² )

BFS 算法求解单源最短路径问题
BFS算法可以用于解决非带权图的单源最短路径问题

void BFS_Min_Distance(Graph G,int u){
    for(int i=0;i<G.vexnum;i++)
        distance[i]=-1;   //初始化距离，-1代表无限大
    visited[u]=TRUE;
    distance[u]=0;          //顶点到自身的距离为0
    EnQueue(Q,u);
    while(!IsEmpty(Q)){
        for(int w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){
                visited[w]=TRUE;
                distance[w]=distance[u]+1;
                EnQueue(Q,w);
            }
        }
    }
}

广度优先生产树
由图的广度优先遍历得到的遍历树称为广度优先生成树

3.2 深度优先搜索(DFS)

#define MaxVertexNum 100
bool visited[MaxVertexNum];
void DFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++)         //初始化访问位
        visited[i]=FALSE;
    for(int i=0;i<G.vexnum;i++){        //遍历
        if(!visited[i])
            DFS(G,i);
    }
}
void DFS(Graph G,int v){
    visit(v);
    visited[i]=TRUE;
    for(int w=FirstNeighbor(G,v);w>=o;w=NextNeighbor(G,v,w)){ //遍历每个邻接顶点，对其进行深度递归
        if(!visited[w])
            DFS(G,w);
    }
}

【注】：由于图的邻接矩阵表示唯一而邻接表表示不唯一，所以基于邻接矩阵的遍历所得DFS序列和BFS序列是惟一的，基于邻接表的遍历得到的DFS序列和BFS序列是不唯一的。

DFS算法性能分析
| |邻接表|邻接矩阵|
|—-|—-|—-|
|时间复杂度| O(V+E )| O(V ² ) |
|空间复杂度| O(V) | O(V) |
深度优先生成树和生成森林
只有对连通图调用DFS才生成深度优先生成树，否则产生的是深度优先生成森林。

3.3 图的遍历与图的连通性

无向连通图：一次遍历即可访问全部顶点。
无向非连通图：遍历次数等于连通分量的数目。
有向强连通图：一次遍历即可访问全部顶点。
有向非强连通图：遍历次数等于强连通分量的数目。

4 图的应用

4.1 最小生成树(MST)

一个连通图的生成树是图的极小连通子图，它包含图中所有顶点，且只含尽可能少的边。
一个带权连通图中，边权总和最小的生成树称为它的最小生成树。
最小生成树有以下性质：

- 树形不唯一
- 边权总和唯一且最小
- 边数为定点数减1

最小生成树通用算法伪代码：

Generate_MST(G){
    T=NULL;
    while(T未形成一颗生成树){
        找到一条加入树T后不会产生回路的最小代价边；
        将该边加入到树T中；
    }
}

最小生成树算法主要有Prim算法和Kruskal算法。

普里姆(Prim)算法

void Prim(G,T){
    T=∅;                //初始化空树
    U={w}；              //U用于存放生成树的顶点，初始化时添加第一个顶点w
    while((V-U)!=∅){     //V用于存放图的全部顶点，若树中不包含全部顶点，就进行循环
        寻找顶点u∈U，顶点v∈(V-U)，且(u,v)的边权最小；
        T=T∪(u,v);        //边并入生成树
        U=U∪{v}；         //顶点并入树的顶点集
    }
}

Prim算法的时间复杂度为O(|V| ² )

克鲁斯卡尔(Kruskal)算法

void Kruskal(V,T){          //V为图的顶点集，T为最小生成树
    T=V；                    //初始化生成树，仅包含全部顶点
    disconnect_num=n;       //T中不连通分量的个数，初始时与顶点数相同
    while(disconnect_num>1){ //不连通分量为1时，T已经建成
        从边集E中取出权值最小的边(v,u);
        if(v和u属于不同的连通分量){
            T=T∪(v,u);              //将此边并入T中
            disconnect_num--;       //不连通分量树数减1
            E=E-(v,u);              //将此边从边集中删除
        }
    }
}

Kruskal算法的时间复杂度是O( |E|log|E| )

4.2 最短路径

　　带权路径长度最短的路径称为最短路径。
　　求解单源最短路径的算法：Dijkstra算法。
　　求解每一对顶点间的最短路径：Floyd算法。

Dijkstra算法

初始条件：
- 图的顶点集为V；
- 图采用邻接矩阵表示array[n][n];
- 从原点到各个顶点的最短路径长度存储在数组distance[n]中；
- 集合S记录已经求得最短路径的顶点。　
算法步骤：
1. 初始化：集合S初始为{0}，distance[i]的初始值为array[0][i];
2. 从顶点集V-S中选出一个顶点vj，从源点v0到它的距离最短，令S=S∪{j}；
3. 修改从源点出发到集合V-S上任一顶点的当前最短路径;
4. 重复步骤2和3，直到所有顶点都包含在S中
  步骤3中的公式：if(distance[k]>distance[j]+array[j][k]) then distance[k]=distance[j]+array[j][k]
局限性：不能处理边权为负数的情况。

4.3 拓扑排序

　　有向无环图(DAG)：一个有向图中不存在环，则称为有向无环图。
　　AOV网：有向无环图中，用顶点表示活动，用有向边表示活动的先后关系，则这样的右向图称为AOV网。
　　拓扑排序：拓扑排序是有向无环图的一个顶点序列，它满足：每个顶点只出现一次，且若存在一条从A到B的路径，则在序列中B出现在A之后。
　　有向无环图拓扑排序的步骤：

    1. 选择一个没有前驱的顶点并输出
    2. 从图中删除该顶点和以它为起点的有向边
    3. 重复步骤1和2直到DAG图为空

4.4 关键路径

　　AOE网：带权有向图中，以顶点表示事件，有向边表示活动，边上权值表示活动开销，则这种有向图称为AOE网。
　　AOE网性质：
　　　　某顶点事件发生后，以该顶点出发的有向边活动才能进行。
　　　　进入某一顶点的有向边活动全部完成，该顶点事件才能发生。
　　关键路径：AOE网中具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。
　　关键变量：

    1. 事件vk的最早发生时间ve(k)
    2. 事件vk的最迟发生事件vl(k)
    3. 活动ai的最早开始时间e(i)
    4. 活动ai的最迟开始时间l(i)
    5. 一个活动ai的最迟开始时间l(i)和最早开始时间e(i)的差值d(i)=l(i)-e(i)

　　求关键路径的步骤：

    1. 求所有顶点事件的最早开始时间和最迟开始时间
    2. 求所有边活动的最早开始时间和最迟开始时间
    3. 求所有边活动的的差额d(),找出所有d()=0的活动构成关键路径